package MyHashMap.impl;

public class MyHashMap<K,V> implements MyMap {


    private final int DEFAULT_CAPACITY = 16;

    Node[] table = new Node[DEFAULT_CAPACITY];

    // 长度
    private int size = 0;

    static class Node implements Entry {

        int hash;
        Object key;
        Object value;
        Node next;

        public Node(int hash,Object key,Object value,Node next){
            this.hash=hash;
            this.key=key;
            this.value=value;
            this.next=next;
        }
        @Override
        public Object getKey() {
            return key;
        }

        @Override
        public Object getValue() {
            return value;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public Object get(Object key) {
        int hash = hashcode(key);
        int i = indexOf(hash, table.length);
        Node node = table[i];
        while (node!=null) {
            if (node.key.equals(key) && node.hash==hash) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    @Override
    public Object put(Object key, Object value) {
        //首先判断数组中有没有该元素
        int hashcode = hashcode(key);
        int i = indexOf(hashcode, table.length);
        Node node = table[i];
        if (node ==null) {
            // 则说明不存在，即往数组里面添加数据
            table[i] = new Node(hashcode, key, value, null);
            ++size;
        } else {
            // 在链表里面添加 已经发生碰撞了
            //第一个判断是看是否在数组中有相同的key和hash
            if (node.hash == hashcode && node.key == key || node.key.equals(key)) {
                // 此时应该新值替换旧值
                Object oldValue = node.value;
                node.value = value;
                return oldValue;
            }else {
                //否则循环链表
                while (true) {
                    if (node.next==null) {
                        node.next = new Node(hashcode,key,value,null);
                        break;
                    }
                    if (node.next.hash==hashcode && node.next.key==key ||node.next.key.equals(key)) {
                        break;
                    }
                    node = node.next;
                }
            }
        }
        //扩容
        if (size==table.length) {
            Node[] tableNew = new Node[table.length*2];
            System.arraycopy(table,0,tableNew,0,table.length);
            table = tableNew;
        }
        return null;
    }

    public int hashcode(Object key) {
        return key.hashCode();
    }

    //这里给出的索引计算是为了测试碰撞比如 key="1"和key="a"会出现hash碰撞,
    public int indexOf(int hash, int length) {
        return hash % length;
    }

}

















